Dijkstra's Algorithm
Named after its E.W. Dijkstra, who proposed it, Dijkstra’s algorithm
finds the shortest paths in a Graph G = ( V, E ) from a source node to
all other nodes in the graph. Since it is a recursive algorithm on V,
its correctness can be proved by induction. Here is the naďve O( n^2 )
algorithm that I implemented:
Dijkstra's algorithm can be expressed as follows:
- G - arbitrary connected graph
- v0 - is the start vertex
- V - is the set of all vertices in G
- S - set of all vertices with p
- d - array of best estimates of shortest path to each vertex
- pi - array of predecessors for each vertex
The basic procedure is as follows:
- Initialize d and pi,
- Set S to empty,
- While V-S not empty,
- Sort vertices in V-S according to best estimates of distance
to source
- Add u, the closest vertex in V-S, to S
- Relax all the vertices still in V-S connected to u.
The Relax procedure is as follows:
For two connected nodes u and v, if the estimate of the distance
from the source to the current node u is greater than the distance
if the path proceeds through v, then make v the predecessor of u and
update the distance estimate.
Dijstra’s Algorithm can be
optimized by using a heap to hold the vertices remaining to be
processed. Doing so means the ExtractMin() operation will take O( log n
) time instead of O( n ) time. Hence, Dijkstra's algorithm can be made
to run in O( n log n ) time.
HOME | PREV |
NEXT
|